package com.leetcode.algorithm.y22.m06;

/**
 * 91. 解码方法
 * 
 * https://leetcode.cn/problems/decode-ways/
 * 
 * @author jie.deng
 *
 */
class Question0091Solution01 {

	public int numDecodings(String s) {
		// '1','2',...'10',...'20',...'26'
		int len = s.length();
		// DP状态定义
		// dp[i]表示s的后i+1个字符解码方法的总数
		int[] dp = new int[len];
		if (s.charAt(0) == '0') {
			return 0;
		}
		// DP状态初始化
		dp[0] = s.charAt(len - 1) == '0' ? 0 : 1;

		// DP状态转移方程
		for (int i = len - 2; i >= 0; i--) {
			int dpIdx = len - 1 - i;
			if (s.charAt(i) == '0') {
				dp[dpIdx] = 0;
				if (s.charAt(i - 1) != '1' && s.charAt(i - 1) != '2') {
					return 0;
				}
			} else if (s.charAt(i) == '1' || (s.charAt(i) == '2' && s.charAt(i + 1) - '0' <= 6)) {
				dp[dpIdx] = dp[dpIdx - 1] + (dpIdx - 2 >= 0 ? dp[dpIdx - 2] : 1);
			} else {
				dp[dpIdx] = dp[dpIdx - 1];
			}
		}

		return dp[len - 1];
	}

}